package com.leetcode.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * 
 * 递归搜索跟层次遍历的比较
 * 递归搜索，递归用到了栈空间，空间复杂度比较高，但是速度相比较快。
 * 层次遍历，只利用了一个队列，空间利用相比较小，但是不断的入队出队，消耗了大量的时间。
 *
 */
public class L101对称二叉树 {
	public boolean isSymmetric(TreeNode root) {
//		return compare(root.left, root.right);
		//下面是利用层次遍历，用到队列
		Queue<TreeNode> que = new LinkedList<>();
		/**
		 * 在compare中，每次比较的是A的左跟B的右，比完，再比A的右跟B的左
		 * 根据这个原理，我们每次从队列中弹出两个A和B，入队的时候是把A的左跟B的右一起入队，再把A的右跟B的左一起入队
		 * 就可以达到效果啦
		 */
		que.offer(root.left);
		que.offer(root.right);
		while(!que.isEmpty()) {
			TreeNode n1 = que.poll();
			TreeNode n2 = que.poll();
			//弹出两个后，比较的步骤就跟compare一样了
			if(n1 == null && n2 == null) continue;
			else if(n1 == null || n2 == null) return false;
			else {
				if(n1.val != n2.val) return false;
				//入队
				que.offer(n1.left);
				que.offer(n2.right);
				//再入队
				que.offer(n1.right);
				que.offer(n2.left);
			}
		}
		return true;
	}
	/**
	 * 递归搜索。
	 */
	public boolean compare(TreeNode n1,TreeNode n2) {
		if(n1 == null && n2 == null) return true;//两个都为空，说明是对称的
		else if(n1 == null || n2 == null) return false;//一个不为空，一个为空，肯定不对称。
		else {//两个为空，就需要判断两个的值相不相等
			if(n1.val != n2.val) return false;
			//n1的左跟n2的右比较，比完，再比较n1的右跟n2的左
			if(compare(n1.left, n2.right))
				return compare(n1.right, n2.left);
		}
		return false;
	}

//树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.right = right;
		}
	}
}
